Feasibility pumps are highly effective primal heuristics for mixed-integerlinear and nonlinear optimization. However, despite their success in practicethere are only few works considering their theoretical properties. We show thatfeasibility pumps can be seen as alternating direction methods applied tospecial reformulations of the original problem, inheriting the convergencetheory of these methods. Moreover, we propose a novel penalty framework thatencompasses this alternating direction method, which allows us to refrain fromrandom perturbations that are applied in standard versions of feasibility pumpsin case of failure. We present a convergence theory for the new penalty basedalternating direction method and compare the new variant of the feasibilitypump with existing versions in an extensive numerical study for mixed-integerlinear and nonlinear problems.
展开▼
